A state machine typically comprises a set of states, each of which can process a stream of input, produce a stream of output, and then switch to the next state. State machines are widely used in software program compilation, where most lexical scanners and grammar parsers utilize some sort of a state machine to perform their work. For example, scanners can use a simple state machine in order to perform a lexical analysis of a regular language, while parsers can use a state machine augmented with a stack to perform a grammatical analysis of the language. The implementation of these state machines can be important in determining the running time efficiency and memory consumption of a parser or scanner.
State machines are frequently implemented using table-driven methods. A next state in a state machine can be determined by indexing a table with the current state and other information. Optimizations can be performed to make the tables smaller, but these optimizations may result in slower performance caused by other issues. In order to optimize the performance of state machines, other methods must be used. One way to speed up the execution of a state machine is to implement it directly in executable codes, instead of encoding the state transitions in a table. Each state can be represented by a label or a jump target in a program and the state transition can be determined by using a switch statement based on the value of an expression or similar multi-way branch construction. These state machines can be much faster than table-driven state machines, but the executable codes for the state machines can also become very large and difficult to download or deploy efficiently.